# -*- coding: utf-8 -*-
"""
    Time    : 2021/1/8 5:04 下午
    Author  : Thinkgamer
    File    : 041-缺失的第一个正数.py
    Desc    : https://leetcode-cn.com/problems/first-missing-positive/
"""
"""
给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。
示例1:
输入: [1,2,0]
输出: 3

示例2:
输入: [3,4,-1,1]
输出: 2

示例3:
输入: [7,8,9,11,12]
输出: 1

提示：
你的算法的时间复杂度应为O(n)，并且只能使用常数级别的额外空间。
"""


# 参考题解：https://leetcode-cn.com/problems/first-missing-positive/solution/que-shi-de-di-yi-ge-zheng-shu-by-leetcode-solution/
# 哈希表法
# 1、遍历一次nums 将其中小于等于0的数据改为 -(n+1)
# 2、遍历nums，如果该值为正数，且小于等于n，则将nums中第 该值 - 1 位的数置为 -的
# 3、遍历nums，如果全部都是负数，则返回 N+1，否则返回第一个不为负的数的下标 + 1
# 44ms 37.79% ｜ 14.8mb 9.35%
def first_missing_positive_v1(nums):
	n = len(nums)
	for i in range(n):
		if nums[i] <= 0:
			nums[i] = n + 1
	print(nums)
	
	for i in range(n):
		abs_num = abs(nums[i])
		if abs_num <= n:
			nums[abs_num-1] = -abs(nums[abs_num-1])
	print(nums)

	for i in range(n):
		if nums[i] > 0:
			return i + 1
	return n + 1


# 置换法，将数字放到其对应位置
# 1、遍历一次数组，将数字放置其对应位置，比如 3，应该放在 第2位，注意，置换后可能还会出现需要置换的情况，继续置换，同时需要考虑被置换位是否需要进行置换
# 2、遍历一次数组，第一个对应位不等于其位置 + 1值的话，返回
# 44ms 37.79% | 17.7mb 16.90%
def first_missing_positive_v2(nums):
	n = len(nums)
	for i in range(n):
		while 1 <= nums[i] <= n and nums[i] != i+1 and nums[nums[i]-1] != nums[i]:
			temp = nums[i]
			nums[i] = nums[temp-1]
			nums[temp - 1] = temp
	for i in range(n):
		if nums[i] != i+1:
			return i + 1
	return n + 1


for nums in [[1], [1, 1], [1, 2, 0], [3, 4, -1, 1], [7, 8, 9, 11, 12]]:
	result = first_missing_positive_v2(nums)
	print(result)
